\documentclass{article}

\renewcommand\thesection{\Roman{section}}
\renewcommand\thesubsection{\arabic{subsection}}


\usepackage{geometry}
\geometry{scale=0.7, nohead}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}

\title{\bsc{Projet Lisp : Graphe}}
\author{Elian Loubrie \and Jonathan Nain}
\date{1 Avril 2011}
\begin{document}
 
\maketitle
\newpage
\tableofcontents
\newpage

\section{Etude de l'existant}
Chaque classe possède une méthode (print-object (o stream)) qui permet d’afficher l’objet \textit{o} suivant un format défini dans cette méthode sur la sortie \textit{stream}.
\subsection{label.lisp}
Module qui permet d’attribuer une étiquette à un objet.
\newline
Structure label-mixin :
\begin{itemize}
\item Un champ label
\end{itemize}
\paragraph{Change-label (o label) :}
Remplace le créneau label de l’objet \textit{o} par \textit{label}.
\paragraph{Find-object-from-label (label list \&key test) :}
Retourne par défaut, un objet qui a le label \textit{label}. Si le mot-clé \textit{test} est renseigné, la fonction retourne un objet qui correspond au test.

\subsection{mark.lisp}
Module qui permet d’attribuer une marque à un objet.
\newline
Structure marked-mixin :
\begin{itemize}
\item Un champ mark
\end{itemize}
\paragraph{Mark-object (o) / unmark-object (o) :}
Met le créneau mark de l’objet \textit{o} à T / NIL.
\paragraph{Mark (list) / unmark (list) :}
Met le créneau mark de chaque objet de la liste \textit{list} à T / NIL.

\subsection{number.lisp}
Module qui permet d’attribuer un numéro à un objet.
\newline
Structure num-mixin :
\begin{itemize}
\item Un champ num
\end{itemize}
\paragraph{Change-num (o num) :}
Modifie le créneau num de l’objet \textit{o} et le met à la valeur \textit{num}.
\paragraph{Find-object-from-num (num list \&key test) :}
Renvoie l’objet de la liste \textit{list} dont le créneau \textit{num} correspond au test.

\subsection{weight.lisp}
Module qui permet d’attribuer un poids à un objet.
\newline
Structure weight-mixin : 
\begin{itemize}
  \item Un champ weight
\end{itemize}
\paragraph{Change-weight (o weight) :}
Modifie le créneau weight de l’objet \textit{o} et le met à la valeur \textit{weight}.
\paragraph{Weight (list) :}
Renvoie la somme des champs weight des éléments de la liste.
\paragraph{Fonctions de comparaison :}
Permettent la comparaison des poids de deux objets.

\subsection{node.lisp}
Module qui définie la classe Node (nœud) et les fonctions nécessaires.
\newline
Structure node : 
\begin{itemize}
  \item Un numéro (hérité de num-mixin) 
  \item Un créneau marque (hérité de marked-mixin)
  \item Un label (hérité de label-mixin)
  \item Un poids (hérité de weight-mixin)
  \item Une liste d'arcs sortants
\end{itemize}
\paragraph{Make-labeled-node (num \&optionnal label) :}
Renvoie une instance d'un nœud avec le champ num égal à \textit{num}, et le champ label égal à \textit{label} si celui-ci est renseigné, nil sinon. 
\paragraph{Make-node (num) :}
Appelle la fonction make-labeled-node (num).
\paragraph{Node-remove (node list) :}
Renvoie la liste de nœuds list privée du nœud node.
\paragraph{Node-adjoin (node list) :}
Renvoie la liste de nœuds \textit{list} à laquelle node a été rajouté si il n'y était pas déjà.
\paragraph{Node-union (list1 list2) :}
Renvoie l'union ensembliste des deux listes.
\paragraph{Node-delete-duplicates (list) :}
Supprime les doublons dans la liste de nœuds \textit{list}.
\paragraph{Node-remove-duplicates (list) :}
Renvoie la liste privée de ses doublons.
\paragraph{Node-set-difference (list1 list2) :}
Renvoie la différence ensembliste de \textit{list1} et \textit{list2}.
\paragraph{Node-subsetp (list1 list2) :}
Renvoie T si tous les éléments de \textit{list1} sont présents dans \textit{list2}.

\subsection{arc.lisp}
Module qui définie la classe Arc et les fonctions nécessaires.
\newline
Structure arc : 
\begin{itemize}
  \item Un créneau marque (hérité de marked-mixin)
  \item Un poids (hérité de weight-mixin)
  \item Un noeud de départ
  \item Un noeud d'arrivée
\end{itemize}
\paragraph{Make-arc (origin extremity \&optional weight) :}
Renvoie une instance d'un arc dont le noeud d'origine est initialisé à \textit{origin} et le noeud d'extremité à \textit{extremity}.
\paragraph{Compare-arcs (arc1 arc2) :}
Renvoie T \textit{arc1} et \textit{arc2} sont égaux, NIL sinon.
\paragraph{Inverse-arc (arc) :}
Renvoie une instance d'un arc dont l'origine est l'extrémité de l'arc \textit{arc}, et inversement. 
\paragraph{Mark-arc (arc) / unmark-arc (arc) :}
Met la marque de l'arc \textit{arc} à T / à NIL.
\paragraph{Arc-member (arc list) :}
Renvoie T si l'arc \textit{arc} fait partie de la liste d'arcs \textit{list}.
\paragraph{Arc-adjoin (arc list) :}
Renvoie la liste d'arcs \textit{list} à laquelle \textit{arc} a été rajouté si il n'y était pas déjà.
\paragraph{Arc-remove (arc list) :}
Renvoie la liste d'arcs \textit{list} privée de l'arc \textit{arc}.
\paragraph{Arc-union (list1 list2) :}
Renvoie l'union ensembliste des deux listes.
\paragraph{Arc-delete-duplicates (list) :}
Supprime les doublons dans la liste d'arcs \textit{list}.
\paragraph{Arc-remove-duplicates (list) :}
Renvoie la liste privée de ses doublons.
\paragraph{Arc-set-difference (list1 list2) :}
Renvoie la différence ensembliste de \textit{list1} et \textit{list2}.
\paragraph{Arc-subsetp (list1 list2) :}
Renvoie T si tous les éléments de \textit{list1} sont présents dans \textit{list2}.

\subsection{path.lisp}
Module qui définie la classe Path (chemin) et les fonctions nécessaires.
\newline
Structure path :
\begin{itemize}
  \item Une liste d’arcs
\end{itemize}
\paragraph{Make-path (\&optional arcs) :}
Renvoie une instance de chemin à partir de la liste d’arcs \textit{arcs} si elle est renseignée, sinon, le chemin est vide, la liste est initialisée à NIL.
\paragraph{Path-cons (arc path) :}
Renvoie la liste d’arc composée des arcs de \textit{path} et de l’arc \textit{arc}.
\paragraph{Path-origins (path) :}
Renvoie la liste des origines des arcs du chemin \textit{path}.
\paragraph{Path-extremities (path) :}
Renvoie la liste des extrémités des arcs du chemin \textit{path}.
\paragraph{Get-nodes (path) :}
Renvoie l’union ensembliste des nœuds origines et extrémités des arcs de \textit{path}.
\paragraph{Weight (path) :}
Renvoie la somme des poids des arcs qui composent le chemin \textit{path}.
\paragraph{Path-cycle-p (path) :}
Renvoie T si le chemin \textit{path} est un cycle, NIL sinon.
\paragraph{Arc-union (list1 list2) :}
Renvoie l'union ensembliste des deux listes.

\subsection{graph-model.lisp}
Module qui définie la classe Graph (graphe) et les fonctions nécessaires.
\newline
Structure graph :  
\begin{itemize}
  \item Un créneau orienté 
  \item Une liste de nœuds
  \item Une liste d'arcs
\end{itemize}
\paragraph{Make-graph (\&optional oriented) :}
Renvoie une instance de graph avec le créneau orienté à T s'il n'est pas renseigné à NIL.
\paragraph{Graph-add-node (node g) :}
Ajoute le nœud \textit{node} à la liste de nœuds du graphe \textit{g}.
\paragraph{Find-node (num g) :}
Renvoie l'instance d'un nœud de \textit{g} qui correspond à \textit{num}, NIL si non trouvé.
\paragraph{Graph-create-node (num g \&optional label) :}
Crée un nœud étiqueté si \textit{label} est renseigné, un nœud non étiqueté sinon ; puis l'ajoute à la liste des nœuds du graphe \textit{g}.
\paragraph{Find-add-node (num g \&optional label) :}
Si le nœud n'est pas présent dans le graphe, la fonction appelle (graph-add-node (node g)) pour ajouter le nœud à la liste des nœuds du graphe \textit{g}.
\paragraph{Graph-marked-nodes (g) / graph-unmarked-nodes (g) :}
Renvoie les nœuds de \textit{g} dont le créneau marque est à T / NIL.
\paragraph{Nb-nodes (g) / nb-arcs (g) / nb-edges (g) :}
Renvoie le nombre de nœuds / arcs / arêtes de \textit{g}.
\paragraph{Out-degree (node g) / in-degree (node g) :}
Renvoie le degré sortant / entrant du nœud node de \textit{g}.
\paragraph{Connected-arcs (node g) :}
Renvoie la liste des arcs connectés au nœud \textit{node} du graphe \textit{g}.
\paragraph{Isolated-node-p (node g) :}
Renvoie T si le nœud \textit{node} du graphe \textit{g} est de degré 0, NIL sinon.
\paragraph{Graph-isolated-nodes (g) :}
Renvoie la liste des nœuds isolés du graphe \textit{g}.
\paragraph{Node-in-arcs (node g) :}
Renvoie la liste des arcs entrants sur le nœud \textit{node} du graphe \textit{g}.
\paragraph{Mark-node (node) / unmark-node (node) :}
Met la marque du nœud \textit{node} à T / à NIL.
\paragraph{Node-marked-p (node) :}
Renvoie T si la marque du nœud \textit{node} est à T, NIL sinon.
\paragraph{Graph-unmark-all-nodes (g) / graph-unmark-all-arcs (g) :}
Met la marque de tous les nœuds/arcs du graphe \textit{g} à NIL.
\paragraph{Set-nodes-weight (g \&optional w) / unset-nodes-weight (g) :}
Met le poids de chaque nœud du graphe \textit{g} à \textit{w}/NIL.
\paragraph{Set-arcs-weight (g \&optional w) / unset-arcs-weight (g) :}
Met le poids de chaque arc du graphe \textit{g} à \textit{w}/NIL.
\paragraph{Inverse-arcs-p (arc1 arc2) :}
Renvoie T si l'\textit{arc1} est l'inverse de l'\textit{arc2}, NIL sinon.
\paragraph{Edges-from-arcs (list) :}
Renvoie la liste \textit{list} donc les arcs inverses (inverse l’un de l’autre) se sont vu retiré leur inverse.
\paragraph{Graph-edges (g) :}
Appelle edges-from-arcs sur la liste des arcs du graphe \textit{g}.
\paragraph{Empty-graph-p (g) :}
Renvoie T si le graphe n’a pas de nœud, Nil sinon.
\paragraph{Out-neighbours (node g)/in-neighbours (node g) :}
Renvoie la liste des nœuds suivants/prédécesseurs du nœud \textit{node}.
\paragraph{Neighbours (node g) :}
Renvoie l’union ensembliste des nœuds suivants/prédécesseurs du nœud \textit{node}.
\paragraph{Node-add-arc (arc) :}
Ajoute un arc à la liste des arcs sortants du nœud « origine » de l’arc \textit{arc}.
\paragraph{Graph-add-arc (origin extremity weight g) :}
Crée une instance d’un arc de poids \textit{weight} avec pour origine le nœud \textit{origin}, pour extrémité \textit{extremity}, ajoute cet arc aux arcs sortants du noeud \textit{origin}, puis ajoute cet arc à la liste des arcs de \textit{g}.
\paragraph{Graph-create-arc (g origin extremity weight oriented) :}
Si \textit{origin} et \textit{extremity} sont des nœuds de \textit{g}, appelle (graph-add-arc (origin extremity weight g)), si \textit{oriented} est à NIL, appelle (graph-add-arc (extremity origin weight g)) pour créer l’arc inverse.

\subsection{graph-io.lisp}
\paragraph{Define-save-info (obj) :}
Défini les règles de sauvegarde de la classe \textit{obj}.
\paragraph{Autres fonctions :}
Gèrent les entrées/sorties en rapport avec les graphes.

\section{Liste des fonctionnalités à réaliser (minimum)}
\begin{itemize}
 \item Écrire un module permettant d'entrer les graphes aux formats externes décrits ci-dessus (1).
 \item Changement oriente/non oriente (6).
 \item Inversion des arcs d'un graphe orienté (7).
 \item Calculer le degré sortant (entrant) maximum (minimum) d'un graphe (10).
 \item Décider s'il existe un chemin entre deux nœuds d'un graphe (11).
 \item Trouver les nœuds accessibles à partir d'un nœud donné d'un graphe (16).
 \item Trouver les nœuds connectés à un nœud donné d'un graphe (17).
 \item Calculer un plus court chemin entre deux nœuds d'un graphe arc-valué (24).
\end{itemize}


\section{Fonctionnalités réalisées}
\subsection{Très facile}
\subsubsection{Changement orienté / non orienté (6)}
\paragraph{Make-graph-not-oriented ((g graph)) :}
Les arcs du graphe orienté passé en paramètre sont transformés en arêtes. Ce graphe modifié est ensuite renvoyé. Le premier graphe n'est pas modifié.
\subsubsection{Inversion des arcs d'un graphe orienté (7)}
\paragraph{Reverse-graph-arcs ((g graph))}
Crée un graphe à partir du graphe passé en paramètre dont les arcs du premier sont les arcs inversés du second, c'est à dire que l'origine devient l'extrémité et vice-versa. Le graphe créé est renvoyé. 

\subsection{Facile}
\subsubsection{Écrire un module permettant d'entrer les graphes aux formats externes (1)}
\paragraph{Graph-from-enodes-and-earcs (nodes arcs oriented) :}
Crée un graphe à partir de la liste de nœuds \textit{nodes} et de la liste d'arcs \textit{arcs}. Ce graphe sera orienté si \textit{oriented} est à la valeur T, non orienté s'il est à NIL.

\paragraph{Graph-from-paths (paths oriented)}
Crée un graphe à partir de la liste de chemins \textit{paths}. Si \textit{oriented} est à T, le graphe sera orienté, non orienté s'il est à NIL.

\subsubsection{Calculer le degré sortant (entrant) maximum (minimum) d'un graphe (10)}
\paragraph{Graph-max-out-degree ((g graph) \&key min in) :}
Renvoie par défaut le degré maximum sortant des noeuds du graphe \textit{g}, sinon :
\begin{itemize}
  \item Si \textit{min} est à T, renvoie le degré minimum sortant. 
  \item Si \textit{in} est à T, renvoie le degré maximum entrant. 
  \item Si \textit{min} et \textit{in} sont à T, renvoie le degré minimum entrant.
\end{itemize}

\subsubsection{Décider s'il existe un chemin entre deux nœuds d'un graphe (11)}
\paragraph{Pathway-from-n1-to-n2-p ((n1 node) (n2 node) (g graph)) :}
Renvoie T s'il existe un chemin du nœud \textit{n1} au nœud \textit{n2} dans le graphe \textit{g}, NIL sinon.

\subsection{Moyen}
\subsubsection{Exporter les graphes au format dot et les afficher depuis le programme Lisp avec xpdf par exemple (3)}
\paragraph{Graph-to-dot-format ((g graph)) :}
Crée un fichier au format DOT à partir des arcs du graphe \textit{g}. Crée ensuite un fichier PDF à partir de ce fichier DOT et pour finir, affiche le fichier pdf. 

\subsubsection{Trouver les nœuds accessibles à partir d'un nœud donné d'un graphe (16)}
\paragraph{Accessible-nodes-from ((n node) (g graph)) :}
Retourne la liste des nœuds accessibles depuis le nœud \textit{n} dans le graphe \textit{g}.

\subsubsection{Trouver les nœuds connectés à un nœud donné d'un graphe (17)}
\paragraph{Connected-nodes ((n node) (g graph)) :}
Retourne la liste des nœuds connectés au nœud \textit{n} dans le graphe \textit{g}.

\subsubsection{Décider si un graphe est connexe (19)}
\paragraph{Connex-p ((g graph)) :}
Renvoie T si le graphe \textit{g} est connexe, NIL sinon.

\subsubsection{Trouver tous les chemins entre deux noeuds (23)}
\paragraph{Pathways-from-n1-to-n2 ((n1 node) (n2 node) (g graph)) :}
Retourne la liste de tous les chemins possibles pour aller au nœud \textit{n2} depuis le nœud \textit{n1}. Le graphe \textit{g} doit être orienté, sinon, il y aurait une infinité de chemins.

\subsection{Difficile}
\subsubsection{Calculer un plus court chemin entre deux noeuds d'un graphe arc-valué (24)}
\paragraph{shortest-pathway-from-n1-to-n2 ((n1 node) (n2 node) (g graph)) :}
Retourne le plus court chemin pour aller du nœud \textit{n1} au nœud \textit{n2} dans le graphe \textit{g}. Là aussi, le graphe doit être orienté, cette fonction renvoie le plus court des chemins calculés grâce à la fonction ci-dessus.

\subsubsection{Calculer l'arbre couvrant de poids minimum d'un graphe arc-valué (27)}
\paragraph{minimum-spanning-tree ((g graph)) :}
Retourne l'arbre couvrant de poids minimum du graphe \textit{g}. Utilise l'algorithme de Kruskal.

\section{Difficultés rencontrées}
La première difficulté que nous avons rencontré a été de comprendre le code déjà existant, les différentes fonctions, ce qui était réalisable avec celles-ci, ce qui ne l'était pas. 
\newline
Dans certains cas, il nous a fallu rechercher des fonctions dans la HyperSpec. Par exemple pour comprendre les fonctions déjà existantes.
\newline
Il nous a aussi été compliqué d'implémenter les algorithmes que nous avons appris en Algo2 dans le langage LISP. 
En effet, il a fallu comprendre exactement ce que produisait une boucle \textit{loop}.
Une boucle \textit{loop} du type \textit{(loop for arc in arcs corps)} n'évalue qu'une seule fois \textit{arcs}.
Avec \textit{arcs} étant la liste des arcs du graphe. 
Si dans la boucle on modifie cette liste d'arcs, la variable \textit{arc} qui prend à chaque itération la valeur suivante de la liste d'arcs ne prendra jamais la valeur des arcs ajoutés à la liste dans la boucle. 
Pour prendre en compte les changements de la liste, il faut utiliser une boucle du type \textit{(loop as arc = (car arcs) corps)}.

\section{Améliorations possibles}
Pour améliorer notre code, on pourrait rendre les fonctions plus lisibles, en les divisant en sous-fonctions monotâches avec des noms explicites.
\newline
Il est certainement possible d'améliorer la complexité des différentes fonctions que nous avons créées pour une utilisation optimale.
\newline
On peut aussi diminuer la redondance de code. En effet, nous n'avons pas toujours utilisé les fonctions de l'existant, nous les avons donc recréées.
\newline
On peut encore améliorer notre projet en implémentant l'ensemble des fonctionnalités demandées, et un maximum d'autres algorithmes de graphes.
\newline
Aussi, pour les algorithmes complexes de graphe que nous avons implémentés, nous n'avons pas réussi au premier abord à utiliser la classe Path, nous avons donc renoncé vu que notre temps était limité. Cependant l'adaptation ne doit pas être compliquée.

\end{document}
